﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0052_MinimumTotal : IAlgorithm
    {
        // 120. 三角形最小路径和

        // 给定一个三角形 triangle ，找出自顶向下的最小路径和。

        // 每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。
        // 也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。

        // 提示：
        //  1 <= triangle.length <= 200
        //  triangle[0].length == 1
        //  triangle[i].length == triangle[i - 1].length + 1
        //  -10^4 <= triangle[i][j] <= 10^4

        public void Test()
        {
            // 算法参数定义
            var triangle = new List<IList<int>> {
                new List<int>{ 2 },
                new List<int>{ 3, 4},
                new List<int>{ 6, 5, 7},
                new List<int>{ 4, 1, 8, 3 }
            };
            // 算法执行与打印
            Console.WriteLine(MinimumTotal1(triangle));
        }

        // 算法
        public int MinimumTotal(IList<IList<int>> triangle)
        {
            if (triangle.Count == 1)
                return triangle[0][0];
            var dp = new int[triangle.Last().Count];
            dp[0] = triangle[0][0];
            int min = 0;
            for (int i = 1; i < triangle.Count; i++)
            {
                var temp = dp.Clone() as int[];
                for (int j = 0; j < triangle[i].Count; j++)
                {
                    if (j == 0)
                        dp[j] = triangle[i][j] + temp[j];
                    else if (j == triangle[i].Count - 1)
                        dp[j] = triangle[i][j] + temp[j - 1];
                    else
                        dp[j] = triangle[i][j] + Math.Min(temp[j - 1], temp[j]);
                    if (i == triangle.Count - 1)
                        if (j == 0)
                            min = dp[j];
                        else
                            min = Math.Min(dp[j], min);
                }
            }
            return min;
        }

        // 优化
        public int MinimumTotal1(IList<IList<int>> triangle)
        {
            if (triangle.Count == 1)
                return triangle[0][0];
            var dp = new int[triangle.Last().Count];
            dp[0] = triangle[0][0];
            int min = 0;
            for (int i = 1; i < triangle.Count; i++)
            {
                dp[i] = dp[i - 1] + triangle[i][i];
                min = dp[i];
                for (int j = i - 1; j >= 0; j--)
                {
                    if (j == 0)
                        dp[0] += triangle[i][j];
                    else
                        dp[j] = triangle[i][j] + Math.Min(dp[j - 1], dp[j]);
                    min = Math.Min(dp[j], min);
                }
            }
            return min;
        }
    }
}
